package com.hsc.offer;

import com.sun.org.apache.bcel.internal.generic.NEW;

import java.util.ArrayList;

/**
 * @author
 * @date 2025-07-07
 * @Description // 23、输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。 路径定义为:从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
 */
public class OfferTest18 {
    public static void main(String[] args) {
        // 创建一个二叉树
        TreeNode_1 node1 = new TreeNode_1(1);
        TreeNode_1 node2 = new TreeNode_1(2);
        TreeNode_1 node3 = new TreeNode_1(3);
        TreeNode_1 node4 = new TreeNode_1(4);
        TreeNode_1 node5 = new TreeNode_1(6);
        TreeNode_1 node6 = new TreeNode_1(5);
        TreeNode_1 node7 = new TreeNode_1(6);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

//        deepSearch(node1);
//        deepSearch(node1 ,9);
        FindPath(node1, 9);

    }

    // 输入一颗二叉树的跟节点和一个整数，
    // 打印出二叉树中结点值的和为输入整数的所有路径。
    // 路径定义为:从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
    // 这里我们使用一个逆向的思维：
    // 使用目标值减去去路径上的每一个元素，如果减到最后一个节点等于递减的结果，说明当前的路径是满足的
    // 举例：假设，我们依次遍历节点，路径为：1,2,4  目标值为9
    // 9与1比 不相等 ，传递 9-1
    // 2节点与8比，不相等，传递8-2
    // 4节点与6比，不相等，说明当前的路径不是满足的要求的，返回空集合
    // 路径为：1,2,6
    // 1节点与9比 不想等于 ，往下转 9-1=8
    // 2节点与8比，不相等，往下穿8-2=6
    // 3节点与8相比，相等，满足条件，返回装好的路径信息
    public static ArrayList<ArrayList<Integer>> FindPath(TreeNode_1 root, int target) {
        // 创建一个结果数组，用来装所有的路径集合 类似二维数组
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        System.out.println(result);
        // 1、如果传入的根节点为null 直接 返回null 集合
        if (root == null) {
            // 情况一：给的树节点本身就是 null 的，就会直接返回
            // 情况二：递归到最后的叶子节点了，他们的左节点和右节点也为null 直接返回
            return result;
        }
        // 如果根节点等于目标值，说明满足要求，当前节点的路径符号要求 保存当前节点
        // root.left == null && root.right == null 左节点为null  右节点也为null 说明找到路径的最后一个节点了
        if (root.val == target && root.left == null && root.right == null) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(root.val);
            result.add(list);
            return result;
        }
        // 如果当前节点的值 小于目标值 说明是符合的路径 但是需要继续往下判断 判断最后一个值是否满足要求
        if (root.val < target) {
            // 递归左子树
            ArrayList<ArrayList<Integer>> left = FindPath(root.left, target - root.val);
            System.out.println(left);
            result.addAll(left);
            // 递归右子树
            ArrayList<ArrayList<Integer>> right = FindPath(root.right, target - root.val);
            result.addAll(right);
            System.out.println(right);
            // 遍历当前节点的左子树 递归弹栈 拿到返回值 并且添加到 路径的集合中
            // 因为我们要的路径是[1,2,6] 然而弹栈时是相反的 6,2,1，所以我们进行递归进行方法返回时 要把返回直接放在每个集合的第0位
            // 将当前值 添加在之前返回的集合的前面
            for (ArrayList<Integer> list : result) {
                list.add(0, root.val);
            }
        }
        // 遍历当前节点的右子树
        // 如果不满足 root.val < target 直接返回 result result 为null
        return result;
    }


    /**
     * 二叉树深度优先搜索
     *
     * @param root
     */
    public static void deepSearch(TreeNode_1 root) {
        // 如果传入的根节点为null
        if (root == null) {
            // 如果当前为null  直接返回
            return;
        }
        // 如果当前节点值为目标值  返回
        if (root != null) {
            System.out.println(root.val);
        }
        // 遍历左子树节点
        deepSearch(root.left);
        // 遍历右子树节点
        deepSearch(root.right);


    }

    // 使用深度优先搜索 也就是前序遍历 判断目标值是否在树上
    public static boolean deepSearch(TreeNode_1 root, int target) {
        // 终止条件：遇到 null 节点时立即返回
        if (root == null) {
            // 如果当前为null  直接返回
            return false;
        }
        System.out.println(root.val);

        if (root.val == target) {
            return true;
        }
        // 如果当前节点值为目标值  返回
        // 遍历左子树节点 遍历右子树节点
        return deepSearch(root.left, target) || deepSearch(root.right, target);
    }


}

class TreeNode_1 {
    int val = 0;
    TreeNode_1 left = null;
    TreeNode_1 right = null;

    public TreeNode_1(int val) {
        this.val = val;

    }

}
